{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Submatrix With Rearrangements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #matrix #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #矩阵 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestSubmatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重新排列后的最大子矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二进制矩阵 <code>matrix</code> ，它的大小为 <code>m x n</code> ，你可以将 <code>matrix</code> 中的 <strong>列</strong> 按任意顺序重新排列。</p>\n",
    "\n",
    "<p>请你返回最优方案下将 <code>matrix</code> 重新排列后，全是 <code>1</code> 的子矩阵面积。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/17/screenshot-2020-12-30-at-40536-pm.png\" style=\"width: 300px; height: 144px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>matrix = [[0,0,1],[1,1,1],[1,0,1]]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>你可以按照上图方式重新排列矩阵的每一列。\n",
    "最大的全 1 子矩阵是上图中加粗的部分，面积为 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/17/screenshot-2020-12-30-at-40852-pm.png\" style=\"width: 500px; height: 62px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>matrix = [[1,0,1,0,1]]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>你可以按照上图方式重新排列矩阵的每一列。\n",
    "最大的全 1 子矩阵是上图中加粗的部分，面积为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>matrix = [[1,1,0],[1,0,1]]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>由于你只能整列整列重新排布，所以没有比面积为 2 更大的全 1 子矩形。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>matrix = [[0,0],[0,0]]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>由于矩阵中没有 1 ，没有任何全 1 的子矩阵，所以面积为 0 。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == matrix.length</code></li>\n",
    "\t<li><code>n == matrix[i].length</code></li>\n",
    "\t<li><code>1 <= m * n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>matrix[i][j]</code> 要么是 <code>0</code> ，要么是 <code>1</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-submatrix-with-rearrangements](https://leetcode.cn/problems/largest-submatrix-with-rearrangements/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-submatrix-with-rearrangements](https://leetcode.cn/problems/largest-submatrix-with-rearrangements/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0,1],[1,1,1],[1,0,1]]', '[[1,0,1,0,1]]', '[[1,1,0],[1,0,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [0] * n \n",
    "        ans = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[j] = dp[j] + 1 if matrix[i][j] == 1 else 0\n",
    "            for k, cnt in enumerate(sorted(dp, reverse=True)):\n",
    "                ans = max(ans, cnt * (k + 1))\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        r, c = len(matrix), len(matrix[0])\n",
    "\n",
    "        def f(nums):  # nums[i] 表示i处的高， 返回可以任意排列 nums， 返回最大的矩阵面积\n",
    "            ll = sorted(nums)\n",
    "            res = 0\n",
    "            for i, x in enumerate(ll):\n",
    "                res = max(res, x * (c - i))  # 面积为 底 * 高， 高为 x，底为 [i, c - 1]\n",
    "            return res\n",
    "        ans = 0\n",
    "        l = [0] * c\n",
    "        for x in matrix:\n",
    "            for j in range(c):\n",
    "                if x[j] == 0:\n",
    "                    l[j] = 0\n",
    "                else:\n",
    "                    l[j] += x[j]\n",
    "            ans = max(ans, f(l))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [0] * n \n",
    "        ans = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[j] = dp[j] + 1 if matrix[i][j] == 1 else 0\n",
    "            for k, cnt in enumerate(sorted(dp, reverse=True)):\n",
    "                ans = max(ans, cnt * (k + 1))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        pre = [0] * n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]:\n",
    "                    pre[j] += 1\n",
    "                else:\n",
    "                    pre[j] = 0\n",
    "            \n",
    "            cur = sorted(pre)\n",
    "            for j in range(n):\n",
    "                if cur[j]:\n",
    "                    ans = max(ans, cur[j] * (n - j))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix) -> int:\n",
    "        if not matrix: return 0\n",
    "        m, n, max_res=len(matrix), len(matrix[0]), 0\n",
    "        x=[0 for _ in range(n)]\n",
    "        for r in range(m):\n",
    "            # 更新直方图向量x：如果当前第r行对应元素是1 则与前一行结果累加 否则变0\n",
    "            x=[matrix[r][j]+x[j] if matrix[r][j]==1 else 0 for j in range(n)]\n",
    "            max_res=max(max_res, self.largestSubvector(x))\n",
    "        return max_res\n",
    "    # 比如 x=[2,0,3] 重排后最大是[3,2,0]的前两个构成2*2矩形 应该返回4 \n",
    "    def largestSubvector(self, x):\n",
    "        sorted_x, max_res=sorted(x,reverse=True), 0\n",
    "        for j in range(len(x)): \n",
    "            max_res=max(max_res, sorted_x[j]*(j+1))\n",
    "        return max_res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        #这道题就是一句：不会！\n",
    "        #来看他干了什么吧\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        #m列高，n行宽\n",
    "        res=0\n",
    "        #答案，也就是最大值\n",
    "        arr=[0]*(n)\n",
    "        #行宽长度的数组\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]==1:\n",
    "                    arr[j]+=1\n",
    "                else:\n",
    "                    arr[j]=0\n",
    "            #求出每一列有多少个1，排序\n",
    "            tmp=sorted(arr,reverse=True)\n",
    "            for j in range(n):\n",
    "                res=max(res,tmp[j]*(j+1))\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [0] * n \n",
    "        ans = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[j] = dp[j] + 1 if matrix[i][j] == 1 else 0\n",
    "            for k, cnt in enumerate(sorted(dp, reverse=True)):\n",
    "                ans = max(ans, cnt * (k + 1))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        res=0\n",
    "        arr=[0]*(n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]==1:\n",
    "                    arr[j]+=1\n",
    "                else:\n",
    "                    arr[j]=0       \n",
    "            tmp=sorted(arr,reverse=True)\n",
    "            for j in range(n):\n",
    "                res=max(res,tmp[j]*(j+1)) \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "    \n",
    "      m,n=len(matrix),len(matrix[0])\n",
    "      \n",
    "      lines=[0]*n\n",
    "      \n",
    "      mx=0\n",
    "      \n",
    "      for r in range(m):\n",
    "      \n",
    "        for c in range(n):\n",
    "        \n",
    "          lines[c]=lines[c]+1 if matrix[r][c] else 0\n",
    "      \n",
    "        lines_c=copy.copy(lines)\n",
    "      \n",
    "        lines_c.sort(reverse=True)\n",
    "      \n",
    "        for i in range(n):\n",
    "      \n",
    "          mx=max(mx,(i+1)*lines_c[i])\n",
    "      \n",
    "      return mx\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        a = [0] * m \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j]: a[j] += 1\n",
    "                else: a[j] = 0\n",
    "            tmp = a[:]\n",
    "            tmp.sort()\n",
    "            for j in range(m):\n",
    "                res = max(res, tmp[j] * (m - j))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        res=0\n",
    "        arr=[0]*n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]==1:\n",
    "                    arr[j]+=1\n",
    "                else:\n",
    "                    arr[j]=0\n",
    "                    \n",
    "            tmp=sorted(arr,reverse=True)\n",
    "            for j in range(n):\n",
    "                res=max(res,tmp[j]*(j+1))\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        height, width=len(matrix),len(matrix[-1])\n",
    "        \n",
    "        lines=[0]*width\n",
    "        max_area=0\n",
    "        for x in range(height):\n",
    "            for y in range(width):\n",
    "                lines[y] = lines[y] + 1 if matrix[x][y] else 0\n",
    "            \n",
    "            lines_c=copy.copy(lines)\n",
    "            lines_c.sort(reverse=True)\n",
    "            for y in range(width):\n",
    "                max_area=max(max_area, (y+1)*lines_c[y])\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        row_n , col_n = len(matrix[:]),len(matrix[0])\n",
    "        min_number = []\n",
    "        min_row = 0\n",
    "        nod_point = [0]*col_n\n",
    "        ans = 0\n",
    "        for i in range(0 , row_n):\n",
    "            for j in range(col_n):\n",
    "                if matrix[i][j] == 1:\n",
    "                    nod_point[j] += 1\n",
    "                else:\n",
    "                    nod_point[j] = 0\n",
    "\n",
    "            tmp = sorted(nod_point,reverse = True)\n",
    "            for j in range(col_n):\n",
    "                ans = max(ans,tmp[j] * (j+1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        width, height = len(matrix[0]), len(matrix)\n",
    "        for i in range(1, height):\n",
    "            for j in range(width):\n",
    "                if matrix[i][j] == 1:\n",
    "                    matrix[i][j] += matrix[i-1][j]\n",
    "        area = float('-inf')\n",
    "        for i in range(height):\n",
    "            matrix[i].sort()\n",
    "            for j in range(width-1, -1, -1):\n",
    "                area = max(area, matrix[i][j] * (width - j))\n",
    "        return area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        res = 0\n",
    "        # count_matrix = [[0]*n]*m\n",
    "        count_matrix = matrix\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                if count_matrix[i][j] == 1:\n",
    "                    count_matrix[i][j] += count_matrix[i-1][j]\n",
    "        \n",
    "        for i in range(m):\n",
    "            count_matrix[i].sort()\n",
    "            for j in range(n):\n",
    "                if count_matrix[i][j] != 0:\n",
    "                    res = max(res, count_matrix[i][j]*(n-j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        for j in range(n):\n",
    "            for i in range(1, m):\n",
    "                matrix[i][j] += matrix[i - 1][j]\n",
    "        ret = 0\n",
    "        for i in range(m):\n",
    "            f = [0] * n\n",
    "            for j in range(n):\n",
    "                left = i\n",
    "                right = m - 1\n",
    "                while left <= right:\n",
    "                    mid = left + right >> 1\n",
    "                    d = matrix[mid][j] - (matrix[i - 1][j] if i > 0 else 0)\n",
    "                    if d == mid - i + 1:\n",
    "                        left = mid + 1\n",
    "                    else:\n",
    "                        right = mid - 1\n",
    "                f[j] = right - i + 1\n",
    "            f.sort()\n",
    "            for j in range(n):\n",
    "                ret = max(ret, f[j] * (n - j))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        h = len(matrix[0])\n",
    "        res = 0\n",
    "        # 找柱子\n",
    "        for i in range(1,n):\n",
    "            for j in range(h):\n",
    "                if matrix[i][j] == 1:\n",
    "                    matrix[i][j] += matrix[i-1][j]\n",
    "        for i in range(n):\n",
    "            matrix[i].sort()\n",
    "            for j in range(h-1,-1,-1):\n",
    "                he = matrix[i][j]\n",
    "                res = max(res,he*(h-j))\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        ans = 0\n",
    "\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                if matrix[row][col] != 0 and row > 0:\n",
    "                    matrix[row][col] += matrix[row - 1][col]\n",
    "\n",
    "            curr_row = sorted(matrix[row], reverse=True)\n",
    "            for i in range(n):\n",
    "                ans = max(ans, curr_row[i] * (i + 1))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        # https://leetcode.com/problems/largest-submatrix-with-rearrangements/editorial/\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        ans = 0\n",
    "\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                if matrix[row][col] != 0 and row > 0:\n",
    "                    matrix[row][col] += matrix[row - 1][col]\n",
    "\n",
    "            curr_row = sorted(matrix[row], reverse=True)\n",
    "            for i in range(n):\n",
    "                ans = max(ans, curr_row[i] * (i + 1))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 1:\n",
    "                    matrix[i][j] += matrix[i-1][j]\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            matrix[i].sort()\n",
    "            for j in range(n-1, -1, -1):\n",
    "                height = matrix[i][j]\n",
    "                res = max(res, height * (n - j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "\n",
    "        for j in range(col):\n",
    "            for i in range(row):\n",
    "                if i>0 and matrix[i][j]>0 and matrix[i-1][j]>0:\n",
    "                    matrix[i][j]+=matrix[i-1][j]\n",
    "\n",
    "        ans = 0\n",
    "        for row in matrix:\n",
    "            row.sort(reverse=True)\n",
    "            ans = max(ans, max([ii*(i+1) for i,ii in enumerate(row)]))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\r\n",
    "        m, n = len(matrix), len(matrix[0])\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if matrix[i][j] and i :\r\n",
    "                    matrix[i][j] += matrix[i - 1][j]\r\n",
    "        res = 0\r\n",
    "        for i in range(m):\r\n",
    "            matrix[i].sort()\r\n",
    "            mn = inf\r\n",
    "            for j in range(n - 1, -1, -1):\r\n",
    "                mn = min(matrix[i][j], mn)\r\n",
    "                res = max(res, mn * (n - j))\r\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        \n",
    "        # Step 1: 计算每一列上的连续1的最大长度\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 1:\n",
    "                    matrix[i][j] += matrix[i-1][j]\n",
    "        \n",
    "        # Step 2: 对于每一行，将其看作柱状图，找到最大的矩形面积\n",
    "        max_area = 0\n",
    "        for i in range(m):\n",
    "            sorted_row = sorted(matrix[i], reverse=True)\n",
    "            for j in range(n):\n",
    "                max_area = max(max_area, sorted_row[j] * (j+1))\n",
    "        \n",
    "        return max_area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution():\n",
    "\tdef largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "\t\tm=len(matrix)\n",
    "\t\tn=len(matrix[0])\n",
    "\t\tfor j in range(n):\n",
    "\t\t\tcount=0\n",
    "\t\t\tfor i in range(m-1,-1,-1):\n",
    "\t\t\t\tif matrix[i][j]:\n",
    "\t\t\t\t\tcount+=1\n",
    "\t\t\t\t\tmatrix[i][j]=count\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tcount=0\n",
    "\t\tans=0\n",
    "\t\tfor i in range(m):\n",
    "\t\t\tsl=SortedList()\n",
    "\t\t\tfor j in range(n):\n",
    "\t\t\t\tif matrix[i][j]>0:\n",
    "\t\t\t\t\tsl.add(matrix[i][j])\n",
    "\t\t\tsllen=len(sl)\n",
    "\t\t\tfor k in range(sllen-1,-1,-1):\n",
    "\t\t\t\tans=max(ans,sl[k]*(sllen-k))\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        ret = 0\n",
    "        for idx in range(m):\n",
    "            print(matrix[idx])\n",
    "            if idx == 0:\n",
    "                tmpl = matrix[idx]\n",
    "            else:\n",
    "                tmpl = []\n",
    "                for jdx in range(n):\n",
    "                    if matrix[idx][jdx] != 0:\n",
    "                        matrix[idx][jdx] += matrix[idx-1][jdx]\n",
    "                    tmpl.append(matrix[idx][jdx])\n",
    "            # print(tmpl)\n",
    "            tmpl = sorted(tmpl, reverse=True)\n",
    "            # print(tmpl)\n",
    "            # print(\"============\")\n",
    "            for j in range(n):\n",
    "                ret = max(tmpl[j] * (j+1), ret)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        rows = [[0] * n for _ in range(m)]\n",
    "        rows[0] = matrix[0]\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                rows[i][j] = rows[i-1][j] + 1 if matrix[i][j] else 0\n",
    "        # print(rows)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            rows[i].sort()\n",
    "            for j in range(n):\n",
    "                ans = max(ans, rows[i][j] * (n - j))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        up = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                if matrix[i][j] == 0:\n",
    "                    up[i][j] = 0\n",
    "                else:\n",
    "                    if i == 0:\n",
    "                        up[i][j] = 1\n",
    "                    else:\n",
    "                        up[i][j] = up[i-1][j] + 1\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            up[i].sort()\n",
    "            for j in range(n):\n",
    "                res = max(up[i][j] * (n - j), res)\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        up = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for j in range(n):\n",
    "            up[0][j] = matrix[0][j]\n",
    "\n",
    "        for j in range(n):\n",
    "            for i in range(1, m):\n",
    "                if matrix[i][j] == 0:\n",
    "                    up[i][j] = 0\n",
    "                else:\n",
    "                    up[i][j] = up[i-1][j] + 1\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            up[i].sort()\n",
    "            for j in range(n):\n",
    "                res = max(up[i][j] * (n - j), res)\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        rows = [[0] * n for _ in range(m)]\n",
    "        rows[0] = matrix[0]\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                rows[i][j] = rows[i-1][j] + 1 if matrix[i][j] else 0\n",
    "        # print(rows)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            rows[i].sort(reverse=True)\n",
    "            for j in range(n):\n",
    "                if rows[i][j] > 0 and rows[i][j] * (j + 1) > ans:\n",
    "                    ans = rows[i][j] * (j + 1)\n",
    "                # ans = max(ans, rows[i][j] * (n - j))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        rows = [[0] * n for _ in range(m)]\n",
    "        rows[0] = matrix[0]\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                rows[i][j] = rows[i-1][j] + 1 if matrix[i][j] else 0\n",
    "        # print(rows)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            rows[i].sort(reverse=True)\n",
    "            for j in range(n):\n",
    "                if rows[i][j] > 0 and rows[i][j] * (j + 1) > ans:\n",
    "                    ans = rows[i][j] * (j + 1)\n",
    "                # ans = max(ans, rows[i][j] * (n - j))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        rows = [[0] * n for _ in range(m)]\n",
    "        rows[0] = matrix[0]\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                rows[i][j] = rows[i-1][j] + 1 if matrix[i][j] else 0\n",
    "        # print(rows)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            rows[i].sort(reverse=True)\n",
    "            for j in range(n):\n",
    "                if rows[i][j] > 0 and rows[i][j] * (j + 1) > ans:\n",
    "                    ans = rows[i][j] * (j + 1)\n",
    "                # ans = max(ans, rows[i][j] * (n - j))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        # 计算列中连续相邻的长度\n",
    "        con = [[0] * n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            con[0][j] = matrix[0][j]\n",
    "            for i in range(1, m):\n",
    "                con[i][j] = con[i - 1][j] + 1 if matrix[i][j] else 0\n",
    "\n",
    "        # 计算结果\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            lst = sorted(con[i], reverse=True)\n",
    "            for j in range(n):\n",
    "                ans = max(ans, lst[j] * (j + 1))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        # 只能交换列的顺序，必然是连续的1才能形成矩阵\n",
    "        # 显然是用DP解决问题\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        dp = [[matrix[i][j] for j in range(n)] for i in range(m)]\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if dp[i][j] == 1:\n",
    "                    dp[i][j] += dp[i-1][j]\n",
    "        \n",
    "        ans = 0\n",
    "        for row in dp:\n",
    "            row.sort(reverse=True)\n",
    "            for i, x in enumerate(row, 1):\n",
    "                ans = max(ans, i * x)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        if not len(matrix):\n",
    "            return 0\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        up = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]:\n",
    "                    up[i][j] = up[i-1][j] + 1\n",
    "        for i in range(m):\n",
    "            up[i].sort()\n",
    "        \n",
    "        return max(max((n-j) * up[i][j] for j in range(n)) for i in range(m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        heights = [[0 for _ in range(C)] for _ in range(R)]     #每一行的高度数组\n",
    "        for c in range(C):\n",
    "            heights[0][c] = matrix[0][c]\n",
    "        for r in range(1, R):\n",
    "            for c in range(C):\n",
    "                if matrix[r][c] == 1:\n",
    "                    heights[r][c] = heights[r-1][c] + 1\n",
    "                else:\n",
    "                    heights[r][c] = 0\n",
    "\n",
    "        res = 0\n",
    "        for r in range(R):\n",
    "            heights[r].sort()                       #是为了贪心\n",
    "            for c in range(C):\n",
    "                cur_area = heights[r][c] * (C - c)  #当前的高度就是最低了。\n",
    "                res = max(res, cur_area)\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
